/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: XMQ
 * Date: 2022-05-19
 * Time: 14:25
 */

import java.util.concurrent.locks.StampedLock;

//BF算法和KMP算法
/**
 * BF算法： 暴力破解字符串匹配问题
 *KMP算法： 使用next数组来减少匹配次数
 */
public class Test {

    public static void getNext(int[] next,String Sub){
        //通过前一项k值我们可以求出下一项的k值
        next[0] = -1;
        next[1] = 0;
        int i = 2;//后一项的i不知道k值
        int k = 0;//前一项的K
        //遍历子串
        for(;i < Sub.length();i++){
            if(k == -1 || Sub.charAt(k) == Sub.charAt(i-1)){
                next[i] = k+1; //next数组i下标的值在前一个值的基础上加一
                i++;
                k++;
            }else{
                k = next[k];
            }
        }
    }
    public static int KMP(String str,String sub,int pos){
        if(str == null || sub == null){
            return -1;
        }
        int Strlen = str.length();
        int Sublen = sub.length();
        if(Strlen == 0 || Sublen == 0){
            return -1;
        }
        if(pos < 0 || pos >= Strlen) return -1;

        int i = pos; //主串下标
        int j = 0; //子串下标

        int[] next = new int[Sublen];
        getNext(next,sub);//给next数组赋值

        while(i < Strlen && j < Sublen){
            //一开始就匹配失败了
            if((j  == -1 )|| (str.charAt(i) == sub.charAt(j))){
                i++;
                j++;
            }else{
                j = next[j];
            }
        }
        if(i < Strlen){
            return i-j;  //子串走完
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(KMP("ababcabcdasdasd", "abcd",0));
        System.out.println(KMP("asdqdasdqweasda", "asdaf",0));
        System.out.println(KMP("abcdabcdab", "ab",0));
    }
    public static int BF(String str,String sub){
        if(str == null || sub == null){
            return -1;
        }
        if(str.length() == 0 || sub.length() == 0){
            return -1;
        }
        int i = 0;//主串下标
        int j = 0;//子串下标
        while( i < str.length() && j < sub.length()){
            if(str.charAt(i) == sub.charAt(j)){
                i++;
                j++;
            }else{
                i = i-j+1;
                j = 0;
            }
        }
        if(i < str.length()){
            return i-j;  //子串走完
        }
        return -1;
    }
    public static void main1(String[] args) {
        System.out.println(BF("ababcabcdasdasd", "abcd"));
        System.out.println(BF("asdqdasdqweasda", "asdaf"));
        System.out.println(BF("abcdabcdab", "ab"));
    }
}
